This invention relates to a boundary representation (B-rep) solid modeling system, and, more particularly, to a solid modeling system that enables easy building of a solid model through a trial-and-error approach because set operations previously performed can be rapidly deleted or modified.
The solid modeling system is utilized for a design of a product or simulation in the field of design and production, to which the invention can be applied.
A solid model means a three-dimensional model of an object in a computer.
Set operation is widely used as a means for building a solid model. Set operation is a general term for an operation to obtain a union set, a difference set or an intersection set as shown in FIG. 3. A final definition of a geometric model is performed through appropriate set operations on models predefined by a system that are called primitives.
In an application such as product design, it is necessary to build a solid model through a trial-and-error approach. To this end, it is necessary to provide functions that can recover a geometric model by cancelling a modification operation already performed, and to rework the operation. Techniques, which are currently employed to implement such functions, are discussed by exemplifying two typical internal representations of a solid model, that is, CSG (constructive solid geometry) representation and B-rep.
The CSG representation is a representation of what space a desired model occupies by positioning primitives such as a parallelpiped and a cylinder in a space. The geometric model can be represented by a logical binary tree structure of the primitives as shown in FIG. 4.
A geometric model can be easily reshaped because it is necessary only to replace the shapes or positions of the primitives in the binary tree structure, or to rewrite the logical operation. However, the CSG representation has only the logical operations upon the primitives, but does not positively manage boundary data such as what volume is built or what edge is produced as the result of the operation. Many applications require such boundary data, so that, in many cases, calculation is performed consequently to obtain a B-rep from the CSG representation. Therefore, the CSG representation has a problem that many applications cannot directly utilize the boundary data although reshaping or reworking can be easily performed. On the other hand, as shown in FIG. 5, the B-rep represents a volume by relations of connections among elements such as vertexes, edges and faces constituting a geometric model. In the B-rep, when the set operation is applied to two volumes, a new volume is generated. By further processing the resultant new volume, a final geometric model is built. Although such execution of the set operation is similar to that in the CSG representation, a model of the boundary representation retains new boundary data of the result of the set operation as data representing the volume.
To reshape a geometric model in the B-rep, there are two following methods:
(1) Execute modification operations all over again.
(2) Describe a modification operation in an Euler operation, and reshape a geometric model backward by applying reverse operations.
The method (1) is, in correcting the volume, to discard the geometric model being built until that moment, and to execute the operations all over again. To this end, the CSG representation is generally retained as the history of the operations generating the B-rep. Then, a new geometric model is rebuilt by referring to and modifying the CSG representation. However, this method takes much time of calculation because, even if a minor modification is to be made, the amount of processing becomes enormous.
On the other hand, the method (2) defines all operations for modifying a geometric model such as set operations as a macro of basic operations called "Euler operations," and backtracks the course of the modification by utilizing the reversibility of the basic operations. This method appears in publications such as:
M. Mantyla and R. Sulonen, "GWB: A Solid Modeler with the Euler Operators," IEEE Computer Graphics, Vol. 2, No. 7, September, 1982, pp. 17-31.
B. G. Baumgart, "A Polyhedron Representation for Computer Vision,"AFIPS Conf. Proc., Vol. 44, 1975 NCC, pp. 589-596.
The Euler operation is a modification operation used to create a new face by adding edges for example, which maintains the relation of the Euler-Poincare equation: EQU v-e+f=2(s-h)+r,
where v is the number of vertices, e is the number of edges, f is the number of faces, s is the number of shells, h is the number of thruholes, and r is the number of rings (holes in a face).
The Euler operation always accompanies a reverse operation, and an operation described as a macro of a combination of Euler operations can be recovered by backtracking the history of the operations.
In this case, the time required for reworking operations depends on the order of the operation to be reworked. It is easy to return to the state immediately before the operation even if the number of operations increases. But if it is desired to rework an operation performed in an early stage, it is necessary to backtrack to that point through the reverse operations. That is, it is necessary to perform reverse operations of the operations not relating to reworking, and then to return to the current point after completion of the intended reworking by forward operations, which is very time-consuming.
The conventional methods require the solid model to be rebuilt all over again, or the operations to be backtracked sequentially to recover the previous geometric model even if, during building of the solid model, it is intended to modify a part of the model by cancelling the set operations already executed, which requires an enormous amount of calculation.
According to the invention, the calculation time required for cancellation or reworking of the set operation does not depend on the order of the set operation. Therefore, the set operation executed at any given time can be rapidly reworked.